#include<iostream>
using namespace std;

struct TreeNode {
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == NULL)
            return root;
        if (root->val < key)
            root->right = deleteNode(root->right, key);
        else if (root->val > key)
            root->left = deleteNode(root->left, key);
        else {
            TreeNode* node = root->right;
            while (node != NULL&&node->left!=NULL) {
                node = node->left;
            }
            if (node != NULL) {
                node->left = root->left;
                root = root->right;
            }
            else
                root = root->left;
        }
        return root;
    }
};